package org.example.myleet.p1442;

import java.util.*;

/**
 * 4 ms
 * 前缀异或，哈希辅助定位
 */
public class Solution {
//    public int countTriplets(int[] arr) {
//        int reply = 0, len = arr.length;
//        int[] diff = new int[len + 1];
//        for (int i = 1; i <= len; ++i) {
//            diff[i] = diff[i - 1] ^ arr[i - 1];
//        }
//        Map<Integer, List<Integer>> valueIdxListMap = new HashMap<>();
//        for (int k = 0; k <= len; ++k) {
//            List<Integer> idxList = valueIdxListMap.getOrDefault(diff[k], new ArrayList<>());
//            for (int i : idxList) {
//                reply += k - i - 1;
//            }
//            idxList.add(k);
//            valueIdxListMap.put(diff[k], idxList);
//        }
//        return reply;
//    }

    /**
     * 2 ms
     * version 1
     * 前缀异或，双循环刷下标i和k
     */
    public int countTriplets(int[] arr) {
        int reply = 0;
        int[] diff = new int[arr.length + 1];
        diff[0] = arr[0];
        for (int i = 1; i < arr.length; ++i) {
            diff[i] = diff[i - 1] ^ arr[i];
        }
        for (int i = 0; i < arr.length; ++i) {
            for (int k = i + 1; k < arr.length; ++k) {
                if ((diff[i] ^ diff[k] ^ arr[i]) == 0) {
                    reply += k - i;
                }
            }
        }
        return reply;
    }
}
